package vip.zhenzicheng.algorithm.leetcode.array;

/**
 * <a href="https://leetcode.cn/problems/merge-sorted-array/">合并两个有序数组</a>
 * 给定两个递增的数组 nums1 nums2 ,和两个整数 m 和 n , 分别表示 nums1.length nums2.length
 * 合并两个数组，使得合并总数组依然为升序排列
 * 注意：合并后数组内容仍在nums1中，故nums1的长度为m+n，多余元素位为0
 * input1:[1,2,3,0,0,0],input2:[2,5,6],n=3,m=3 -> output:[1,2,2,3,5,6]
 * 边界条件：
 * nums1.length == m + n
 * nums2.length == n
 * 0 <= m, n <= 200
 * 1 <= m + n <= 200
 * -109 <= nums1[i], nums2[j] <= 109
 *
 * @author zhenzicheng
 * @date: 2022-05-31 09:30
 */
public class MergeSortedArray_88 {

  /**
   * 最简单的合并方法，使用自带数组快排，不推荐
   */
  // public void merge(int[] nums1, int m, int[] nums2, int n) {
  //   // 将 nums2 合并到 nums1
  //   for (int i = 0; i < n; i++) {
  //     nums1[m + i] = nums2[i];
  //   }
  //   Arrays.sort(nums1);
  // }

  /**
   * 双指针 + 新数组
   * 缺点：引入了一个新数组
   */
  // public void merge(int[] nums1, int m, int[] nums2, int n) {
  //   if (n == 0) { // 边界
  //     return;
  //   }
  //   int N = m + n;
  //   int[] temp = new int[N]; // 临时空间存数据
  //
  //   for (int cur = 0, mIndex = 0 , nIndex = 0; cur < N; cur++) {
  //     if (mIndex >= m) { // 左边取完直接放右边
  //       temp[cur] = nums2[nIndex++];
  //     } else if (nIndex >= n) { // 右边取完直接放左边
  //       temp[cur] = nums1[mIndex++];
  //     } else if (nums1[mIndex] <= nums2[nIndex]) { // 左边小就放左边
  //       temp[cur] = nums1[mIndex++];
  //     }else {
  //       temp[cur] = nums2[nIndex++];
  //     }
  //
  //   }
  //   System.arraycopy(temp, 0, nums1, 0, N); // 将temp对拷到nums1
  //
  // }

  /**
   * 双指针 + 倒序
   */
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    int N = m + n;
    // 将大数放在右边，倒序遍历nums1，这样结果即为升序并且不需要使用任何的
    for (int cur = N - 1, mIndex = m - 1, nIndex = n - 1; cur >= 0; cur--) {
      if (mIndex < 0) { // 左边取完直接放右边
        nums1[cur] = nums2[nIndex--];
      } else if (nIndex < 0) { // 右边取完直接放左边
        nums1[cur] = nums1[mIndex--];
      } else if (nums1[mIndex] >= nums2[nIndex]) {
        nums1[cur] = nums1[mIndex--];
      } else {
        nums1[cur] = nums2[nIndex--];
      }
    }

  }

}
